﻿/*
 * Diff Match and Patch
 * Copyright 2018 The diff-match-patch Authors.
 * https://github.com/google/diff-match-patch
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using System.Collections.Generic;
using System.Text;
using System.Web;

namespace ExcelMerge;

public enum PatchState
{
    Origin,
    Insert,
    Delete,
    Change
}

public interface IDiffItem<T> : IEquatable<T>
{
    PatchState PatchedState { get; set; }
    bool IsControl();
    bool IsLineFeed();
    bool IsWhiteSpace();
    bool IsLetterOrDigit();
    bool IsBlankLineStart(List<T> list);
    bool IsBlankLineEnd(List<T> list);
    T DeepCopy();
}

public class LineDiffItem(int line) : IDiffItem<LineDiffItem>
{
    public int Line { get; } = line;

    public PatchState PatchedState { get; set; }

    public bool IsControl()
    {
        return false;
    }

    public bool IsLineFeed()
    {
        return false;
    }

    public bool IsWhiteSpace()
    {
        return false;
    }

    public bool IsLetterOrDigit()
    {
        return true;
    }

    public bool IsBlankLineStart(List<LineDiffItem> list)
    {
        return false;
    }

    public bool IsBlankLineEnd(List<LineDiffItem> list)
    {
        return false;
    }

    public LineDiffItem DeepCopy()
    {
        return new LineDiffItem(Line){PatchedState = PatchedState};
    }

    public bool Equals(LineDiffItem? other)
    {
        return Line == other?.Line;
    }

    public override int GetHashCode()
    {
        return Line.GetHashCode();
    }

    public override string ToString()
    {
        return Line.ToString();
    }
}

public class DiffListComparer<T> : IEqualityComparer<List<T>> where T : IDiffItem<T>
{
    public bool Equals(List<T> x, List<T> y)
    {
        if (x == null || y == null)
        {
            return false;
        }

        if (x.Count != y.Count)
        {
            return false;
        }

        for (int i = 0; i < x.Count; i++)
        {
            if (!x[i].Equals(y[i]))
            {
                return false;
            }
        }

        return true;
    }

    public int GetHashCode(List<T> obj)
    {
        var hash = 0;
        foreach (var item in obj)
        {
            hash = HashCode.Combine(hash, item.GetHashCode());
        }

        return hash;
    }
}

/**-
 * The data structure representing a diff is a List of Diff objects:
 * {Diff(Operation.DELETE, "Hello"), Diff(Operation.INSERT, "Goodbye"),
 *  Diff(Operation.EQUAL, " world.")}
 * which means: delete "Hello", add "Goodbye" and keep " world."
 */
public enum Operation
{
    DELETE,
    INSERT,
    EQUAL
}

/**
 * Class representing one diff operation.
 */
public class Diff<T>:IEquatable<Diff<T>> where T : IDiffItem<T>
{
    public Operation operation;

    // One of: INSERT, DELETE or EQUAL.
    public List<T> text;
    // The text associated with this diff operation.

    /**
     * Constructor.  Initializes the diff with the provided values.
     * @param operation One of INSERT, DELETE or EQUAL.
     * @param text The text being applied.
     */
    public Diff(Operation operation, List<T> text)
    {
        // Construct a diff with the specified operation and text.
        this.operation = operation;
        this.text = new(text.Count);
        this.text.AddRange(text);
    }

    /**
     * Display a human-readable version of this Diff.
     * @return text version.
     */
    public override string ToString()
    {
        var sb = new StringBuilder();
        sb.Append("Diff(").Append(operation).Append(',');
        foreach (var item in text)
        {
            sb.Append(item);
        }

        sb.Append(')');
        return sb.ToString();
    }

    public string ToElementString()
    {
        StringBuilder sb = new();
        foreach (var item in text)
        {
            sb.Append(item);
        }

        return sb.ToString();
    }

    /**
     * Is this Diff equivalent to another Diff?
     * @param d Another Diff to compare against.
     * @return true or false.
     */
    public override bool Equals(Object obj)
    {
        if (obj is not Diff<T> p)
        {
            return false;
        }

        if (p.operation != operation)
        {
            return false;
        }

        if (p.text.Count != text.Count)
        {
            return false;
        }

        for (int i = 0; i < text.Count; i++)
        {
            if (!p.text[i].Equals(text[i]))
            {
                return false;
            }
        }

        return true;
    }

    public bool Equals(Diff<T> obj)
    {
        // If parameter is null return false.
        if (obj == null)
        {
            return false;
        }

        if (obj.operation != operation)
        {
            return false;
        }

        if (obj.text.Count != text.Count)
        {
            return false;
        }

        for (int i = 0; i < text.Count; i++)
        {
            if (!obj.text[i].Equals(text[i]))
            {
                return false;
            }
        }

        return true;
    }

    public override int GetHashCode()
    {
        var hash = operation.GetHashCode();
        foreach (var item in text)
        {
            hash = HashCode.Combine(hash, item.GetHashCode());
        }

        return hash;
    }
}

public class Patch<T>:IEquatable<Patch<T>> where T : IDiffItem<T>
{
    public List<Diff<T>> diffs = new();
    public int start; // 原始文本中补丁开始位置
    public int insertLength;
    public int deleteLength;

    /**
     * Emulate GNU diff's format.
     * Header: @@ -382,8 +481,9 @@
     * Indices are printed as 1-based, not 0-based.
     * @return The GNU diff string.
     */
    public override string ToString()
    {
        StringBuilder text = new StringBuilder();
        text.Append("@@ -").Append($"{start},{deleteLength}").Append(" +").Append($"{start},{insertLength}")
            .Append(" @@\n");
        // Escape the body of the patch with %xx notation.
        foreach (var aDiff in diffs)
        {
            switch (aDiff.operation)
            {
                case Operation.INSERT:
                    text.Append('+');
                    break;
                case Operation.DELETE:
                    text.Append('-');
                    break;
                case Operation.EQUAL:
                    text.Append(' ');
                    break;
            }

            text.Append(aDiff.text.ToElementString()).Append('\n');
        }

        return text.ToString();
    }

    public bool Equals(Patch<T> other)
    {
        if (other is null) return false;
        if (ReferenceEquals(this, other)) return true;
        return diffs.ElementEquals(other.diffs) && start == other.start && insertLength == other.insertLength && deleteLength == other.deleteLength;
    }
}

/**
 * Class containing the diff, match and patch methods.
 * Also Contains the behaviour settings.
 */
public class diff_match_patch<T> where T : IDiffItem<T>
{
    // Defaults.
    // Set these on your diff_match_patch instance to override the defaults.

    // Cost of an empty edit operation in terms of edit characters.
    public short Diff_EditCost = 4;

    /**
     * Find the differences between two texts.  Simplifies the problem by
     * stripping any common prefix or suffix off the texts before diffing.
     * @param text1 Old string to be diffed.
     * @param text2 New string to be diffed.
     * @param checklines Speedup flag.  If false, then don't run a
     *     line-level diff first to identify the changed areas.
     *     If true, then run a faster slightly less optimal diff.
     * @param deadline Time when the diff should be complete by.  Used
     *     internally for recursive calls.  Users should set DiffTimeout
     *     instead.
     * @return List of Diff objects.
     */
    public List<Diff<T>> diff_main(List<T> text1, List<T> text2, bool checkLines = true)
    {
        // Check for null inputs not needed since null can't be passed in C#.

        // Check for equality (speedup).
        List<Diff<T>> diffs;
        if (text1.ElementEquals(text2))
        {
            diffs = new List<Diff<T>>();
            if (text1.Count != 0)
            {
                diffs.Add(new(Operation.EQUAL, text1));
            }

            return diffs;
        }

        // Trim off common prefix (speedup).
        int commonlength = diff_commonPrefix(text1.AsSpan(), text2.AsSpan());
        var commonprefix = text1.Slice(0, commonlength);
        text1 = text1.Slice(commonlength);
        text2 = text2.Slice(commonlength);

        // Trim off common suffix (speedup).
        commonlength = diff_commonSuffix(text1.AsSpan(), text2.AsSpan());
        var commonsuffix = text1.Slice(text1.Count - commonlength);
        text1 = text1.Slice(0, text1.Count - commonlength);
        text2 = text2.Slice(0, text2.Count - commonlength);

        // Compute the diff on the middle block.
        diffs = diff_compute(text1, text2, checkLines);

        // Restore the prefix and suffix.
        if (commonprefix.Count != 0)
        {
            diffs.Insert(0, (new(Operation.EQUAL, commonprefix)));
        }

        if (commonsuffix.Count != 0)
        {
            diffs.Add(new(Operation.EQUAL, commonsuffix));
        }

        diff_cleanupMerge(diffs);
        return diffs;
    }

    /**
     * Find the differences between two texts.  Assumes that the texts do not
     * have any common prefix or suffix.
     * @param text1 Old string to be diffed.
     * @param text2 New string to be diffed.
     * @param checklines Speedup flag.  If false, then don't run a
     *     line-level diff first to identify the changed areas.
     *     If true, then run a faster slightly less optimal diff.
     * @param deadline Time when the diff should be complete by.
     * @return List of Diff objects.
     */
    private List<Diff<T>> diff_compute(List<T> text1, List<T> text2, bool checklines)
    {
        var diffs = new List<Diff<T>>();
        if (text1.Count == 0)
        {
            // Just add some text (speedup).
            diffs.Add(new(Operation.INSERT, text2));
            return diffs;
        }

        if (text2.Count == 0)
        {
            // Just delete some text (speedup).
            diffs.Add(new(Operation.DELETE, text1));
            return diffs;
        }

        var longtext = text1.Count > text2.Count ? text1 : text2;
        var shorttext = text1.Count > text2.Count ? text2 : text1;
        int i = longtext.IndexOf(shorttext);
        if (i != -1)
        {
            // Shorter text is inside the longer text (speedup).
            Operation op = (text1.Count > text2.Count) ? Operation.DELETE : Operation.INSERT;
            diffs.Add(new(op, longtext.Slice(0, i)));
            diffs.Add(new(Operation.EQUAL, shorttext));
            diffs.Add(new(op, longtext.Slice(i + shorttext.Count)));
            return diffs;
        }

        if (shorttext.Count == 1)
        {
            // Single character string.
            // After the previous speedup, the character can't be an equality.
            diffs.Add(new(Operation.DELETE, text1));
            diffs.Add(new(Operation.INSERT, text2));
            return diffs;
        }

        // Check to see if the problem can be split in two.
        var hm = diff_halfMatch(text1.AsSpan(), text2.AsSpan());
        if (hm != null)
        {
            // A half-match was found, sort out the return data.
            var text1_a = hm[0];
            var text1_b = hm[1];
            var text2_a = hm[2];
            var text2_b = hm[3];
            var mid_common = hm[4];
            // Send both pairs off for separate processing.
            var diffs_a = diff_main(text1_a, text2_a, checklines);
            var diffs_b = diff_main(text1_b, text2_b, checklines);
            // Merge the results.
            diffs = diffs_a;
            diffs.Add(new(Operation.EQUAL, mid_common));
            diffs.AddRange(diffs_b);
            return diffs;
        }

        if (checklines && text1.Count > 100 && text2.Count > 100)
        {
            return diff_lineMode(text1, text2);
        }

        return diff_bisect(text1, text2);
    }

    /**
     * Do a quick line-level diff on both strings, then rediff the parts for
     * greater accuracy.
     * This speedup can produce non-minimal diffs.
     * @param text1 Old string to be diffed.
     * @param text2 New string to be diffed.
     * @param deadline Time when the diff should be complete by.
     * @return List of Diff objects.
     */
    private List<Diff<T>> diff_lineMode(List<T> text1, List<T> text2)
    {
        // Scan the text on a line-by-line basis first.
        var (line1, line2, lineArray) = diff_linesToChars(text1, text2);
        var diffMatchPatch = new diff_match_patch<LineDiffItem>();
        var lineDiffs = diffMatchPatch.diff_main(line1, line2, false);

        // Convert the diff back to original text.
        var diffs = diff_charsToLines(lineDiffs, lineArray);
        // Eliminate freak matches (e.g. blank lines)
        diff_cleanupSemantic(diffs);

        // Rediff any replacement blocks, this time character-by-character.
        // Add a dummy entry at the end.
        diffs.Add(new(Operation.EQUAL, new()));
        int pointer = 0;
        int count_delete = 0;
        int count_insert = 0;
        var text_delete = new List<T>();
        var text_insert = new List<T>();
        while (pointer < diffs.Count)
        {
            switch (diffs[pointer].operation)
            {
                case Operation.INSERT:
                    count_insert++;
                    text_insert.AddRange(diffs[pointer].text);
                    break;
                case Operation.DELETE:
                    count_delete++;
                    text_delete.AddRange(diffs[pointer].text);
                    break;
                case Operation.EQUAL:
                    // Upon reaching an equality, check for prior redundancies.
                    if (count_delete >= 1 && count_insert >= 1)
                    {
                        // Delete the offending records and add the merged ones.
                        diffs.RemoveRange(pointer - count_delete - count_insert, count_delete + count_insert);
                        pointer = pointer - count_delete - count_insert;
                        var subDiff = diff_main(text_delete, text_insert, false);
                        diffs.InsertRange(pointer, subDiff);
                        pointer += subDiff.Count;
                    }

                    count_insert = 0;
                    count_delete = 0;
                    text_delete.Clear();
                    text_insert.Clear();
                    break;
            }

            pointer++;
        }

        diffs.RemoveAt(diffs.Count - 1); // Remove the dummy entry at the end.

        return diffs;
    }

    /**
     * Find the 'middle snake' of a diff, split the problem in two
     * and return the recursively constructed diff.
     * See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.
     * @param text1 Old string to be diffed.
     * @param text2 New string to be diffed.
     * @param deadline Time at which to bail if not yet complete.
     * @return List of Diff objects.
     */
    protected List<Diff<T>> diff_bisect(List<T> text1, List<T> text2)
    {
        // Cache the text lengths to prevent multiple calls.
        int text1_length = text1.Count;
        int text2_length = text2.Count;
        int max_d = (text1_length + text2_length + 1) / 2;
        int v_offset = max_d;
        int v_length = 2 * max_d;
        int[] v1 = new int[v_length];
        int[] v2 = new int[v_length];
        for (int x = 0; x < v_length; x++)
        {
            v1[x] = -1;
            v2[x] = -1;
        }

        v1[v_offset + 1] = 0;
        v2[v_offset + 1] = 0;
        int delta = text1_length - text2_length;
        // If the total number of characters is odd, then the front path will
        // collide with the reverse path.
        bool front = (delta % 2 != 0);
        // Offsets for start and end of k loop.
        // Prevents mapping of space beyond the grid.
        int k1start = 0;
        int k1end = 0;
        int k2start = 0;
        int k2end = 0;
        for (int d = 0; d < max_d; d++)
        {
            // Walk the front path one step.
            for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2)
            {
                int k1_offset = v_offset + k1;
                int x1;
                if (k1 == -d || k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])
                {
                    x1 = v1[k1_offset + 1];
                }
                else
                {
                    x1 = v1[k1_offset - 1] + 1;
                }

                int y1 = x1 - k1;
                while (x1 < text1_length && y1 < text2_length && text1[x1].Equals(text2[y1]))
                {
                    x1++;
                    y1++;
                }

                v1[k1_offset] = x1;
                if (x1 > text1_length)
                {
                    // Ran off the right of the graph.
                    k1end += 2;
                }
                else if (y1 > text2_length)
                {
                    // Ran off the bottom of the graph.
                    k1start += 2;
                }
                else if (front)
                {
                    int k2_offset = v_offset + delta - k1;
                    if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1)
                    {
                        // Mirror x2 onto top-left coordinate system.
                        int x2 = text1_length - v2[k2_offset];
                        if (x1 >= x2)
                        {
                            // Overlap detected.
                            return diff_bisectSplit(text1, text2, x1, y1);
                        }
                    }
                }
            }

            // Walk the reverse path one step.
            for (int k2 = -d + k2start; k2 <= d - k2end; k2 += 2)
            {
                int k2_offset = v_offset + k2;
                int x2;
                if (k2 == -d || k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])
                {
                    x2 = v2[k2_offset + 1];
                }
                else
                {
                    x2 = v2[k2_offset - 1] + 1;
                }

                int y2 = x2 - k2;
                while (x2 < text1_length && y2 < text2_length &&
                       text1[text1_length - x2 - 1].Equals(text2[text2_length - y2 - 1]))
                {
                    x2++;
                    y2++;
                }

                v2[k2_offset] = x2;
                if (x2 > text1_length)
                {
                    // Ran off the left of the graph.
                    k2end += 2;
                }
                else if (y2 > text2_length)
                {
                    // Ran off the top of the graph.
                    k2start += 2;
                }
                else if (!front)
                {
                    int k1_offset = v_offset + delta - k2;
                    if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1)
                    {
                        int x1 = v1[k1_offset];
                        int y1 = v_offset + x1 - k1_offset;
                        // Mirror x2 onto top-left coordinate system.
                        x2 = text1_length - v2[k2_offset];
                        if (x1 >= x2)
                        {
                            // Overlap detected.
                            return diff_bisectSplit(text1, text2, x1, y1);
                        }
                    }
                }
            }
        }

        // Diff took too long and hit the deadline or
        // number of diffs equals number of characters, no commonality at all.
        var diffs = new List<Diff<T>>
        {
            new(Operation.DELETE, text1),
            new(Operation.INSERT, text2)
        };
        return diffs;
    }

    /**
     * Given the location of the 'middle snake', split the diff in two parts
     * and recurse.
     * @param text1 Old string to be diffed.
     * @param text2 New string to be diffed.
     * @param x Index of split point in text1.
     * @param y Index of split point in text2.
     * @param deadline Time at which to bail if not yet complete.
     * @return LinkedList of Diff objects.
     */
    private List<Diff<T>> diff_bisectSplit(List<T> text1, List<T> text2, int x, int y)
    {
        var text1a = text1.Slice(0, x);
        var text2a = text2.Slice(0, y);
        var text1b = text1.Slice(x);
        var text2b = text2.Slice(y);

        // Compute both diffs serially.
        var diffs = diff_main(text1a, text2a, false);
        var diffsb = diff_main(text1b, text2b, false);

        diffs.AddRange(diffsb);
        return diffs;
    }

    /**
     * Split two texts into a list of strings.  Reduce the texts to a string of
     * hashes where each Unicode character represents one line.
     * @param text1 First string.
     * @param text2 Second string.
     * @return Three element Object array, containing the encoded text1, the
     *     encoded text2 and the List of unique strings.  The zeroth element
     *     of the List of unique strings is intentionally blank.
     */
    protected (List<LineDiffItem> text1, List<LineDiffItem> text2, List<List<T>> lineArray) diff_linesToChars(
        List<T> text1, List<T> text2)
    {
        var lineArray = new List<List<T>>();
        var lineHash = new Dictionary<List<T>, int>(new DiffListComparer<T>());
        // e.g. linearray[4] == "Hello\n"
        // e.g. linehash.get("Hello\n") == 4

        // "\x00" is a valid character, but various debuggers don't like it.
        // So we'll insert a junk entry to avoid generating a null character.
        lineArray.Add(new List<T>());

        // Allocate 2/3rds of the space for text1, the rest for text2.
        var chars1 = diff_linesToCharsMunge(text1, lineArray, lineHash, 40000);
        var chars2 = diff_linesToCharsMunge(text2, lineArray, lineHash, 65535);
        return (chars1, chars2, lineArray);
    }

    /**
     * Split a text into a list of strings.  Reduce the texts to a string of
     * hashes where each Unicode character represents one line.
     * @param text String to encode.
     * @param lineArray List of unique strings.
     * @param lineHash Map of strings to indices.
     * @param maxLines Maximum length of lineArray.
     * @return Encoded string.
     */
    private List<LineDiffItem> diff_linesToCharsMunge(List<T> text, List<List<T>> lineArray,
        Dictionary<List<T>, int> lineHash, int maxLines)
    {
        int lineStart = 0;
        int lineEnd = -1;
        var lines = new List<LineDiffItem>();
        // Walk the text, pulling out a Substring for each line.
        // text.split('\n') would would temporarily double our memory footprint.
        // Modifying text would create many large strings to garbage collect.
        while (lineEnd < text.Count - 1)
        {
            lineEnd = -1;
            for (int i = lineStart; i < text.Count; i++)
            {
                if (text[i].IsLineFeed())
                {
                    lineEnd = i;
                    break;
                }
            }

            if (lineEnd == -1)
            {
                lineEnd = text.Count - 1;
            }

            var line = text.Slice(lineStart, lineEnd + 1 - lineStart);
            if (lineHash.ContainsKey(line))
            {
                lines.Add(new(lineHash[line]));
            }
            else
            {
                if (lineArray.Count == maxLines)
                {
                    // Bail out at 65535 because char 65536 == char 0.
                    line = text.Slice(lineStart);
                    lineEnd = text.Count;
                }

                lineArray.Add(line);
                lineHash.Add(line, lineArray.Count - 1);
                lines.Add(new(lineArray.Count - 1));
            }

            lineStart = lineEnd + 1;
        }

        return lines;
    }

    /**
     * Rehydrate the text in a diff from a string of line hashes to real lines
     * of text.
     * @param diffs List of Diff objects.
     * @param lineArray List of unique strings.
     */
    protected List<Diff<T>> diff_charsToLines(ICollection<Diff<LineDiffItem>> diffs, IList<List<T>> lineArray)
    {
        var result = new List<Diff<T>>();
        foreach (var diff in diffs)
        {
            var d = new Diff<T>(diff.operation, new List<T>());
            for (int j = 0; j < diff.text.Count; j++)
            {
                d.text.AddRange(lineArray[diff.text[j].Line]);
            }

            result.Add(d);
        }

        return result;
    }

    /**
     * Determine the common prefix of two strings.
     * @param text1 First string.
     * @param text2 Second string.
     * @return The number of characters common to the start of each string.
     */
    public int diff_commonPrefix(ReadOnlySpan<T> text1, ReadOnlySpan<T> text2)
    {
        // Performance analysis: https://neil.fraser.name/news/2007/10/09/
        int n = Math.Min(text1.Length, text2.Length);
        for (int i = 0; i < n; i++)
        {
            if (!text1[i].Equals(text2[i]))
            {
                return i;
            }
        }

        return n;
    }

    /**
     * Determine the common suffix of two strings.
     * @param text1 First string.
     * @param text2 Second string.
     * @return The number of characters common to the end of each string.
     */
    public int diff_commonSuffix(ReadOnlySpan<T> text1, ReadOnlySpan<T> text2)
    {
        // Performance analysis: https://neil.fraser.name/news/2007/10/09/
        int text1_length = text1.Length;
        int text2_length = text2.Length;
        int n = Math.Min(text1.Length, text2.Length);
        for (int i = 1; i <= n; i++)
        {
            if (!text1[text1_length - i].Equals(text2[text2_length - i]))
            {
                return i - 1;
            }
        }

        return n;
    }

    /**
     * Determine if the suffix of one string is the prefix of another.
     * @param text1 First string.
     * @param text2 Second string.
     * @return The number of characters common to the end of the first
     *     string and the start of the second string.
     */
    protected int diff_commonOverlap(List<T> text1, List<T> text2)
    {
        // Cache the text lengths to prevent multiple calls.
        int text1_length = text1.Count;
        int text2_length = text2.Count;
        // Eliminate the null case.
        if (text1_length == 0 || text2_length == 0)
        {
            return 0;
        }

        // Truncate the longer string.
        if (text1_length > text2_length)
        {
            text1 = text1.Slice(text1_length - text2_length);
        }
        else if (text1_length < text2_length)
        {
            text2 = text2.Slice(0, text1_length);
        }

        int text_length = Math.Min(text1_length, text2_length);
        // Quick check for the worst case.
        if (text1.ElementEquals(text2))
        {
            return text_length;
        }

        // Start by looking for a single character match
        // and increase length until no match is found.
        // Performance analysis: https://neil.fraser.name/news/2010/11/04/
        int best = 0;
        int length = 1;
        while (true)
        {
            var pattern = text1.Slice(text_length - length);
            int found = text2.IndexOf(pattern);
            if (found == -1)
            {
                return best;
            }

            length += found;
            if (found == 0 || text1.Slice(text_length - length).ElementEquals(text2.Slice(0, length)))
            {
                best = length;
                length++;
            }
        }
    }

    /**
     * Do the two texts share a Substring which is at least half the length of
     * the longer text?
     * This speedup can produce non-minimal diffs.
     * @param text1 First string.
     * @param text2 Second string.
     * @return Five element String array, containing the prefix of text1, the
     *     suffix of text1, the prefix of text2, the suffix of text2 and the
     *     common middle.  Or null if there was no match.
     */
    protected List<T>[] diff_halfMatch(ReadOnlySpan<T> text1, ReadOnlySpan<T> text2)
    {
        var longText = text1.Length > text2.Length ? text1 : text2;
        var shortText = text1.Length > text2.Length ? text2 : text1;
        if (longText.Length < 4 || shortText.Length * 2 < longText.Length)
        {
            return null; // Pointless.
        }

        // First check if the second quarter is the seed for a half-match.
        var hm1 = diff_halfMatchI(longText, shortText, (longText.Length + 3) / 4);
        // Check again based on the third quarter.
        var hm2 = diff_halfMatchI(longText, shortText, (longText.Length + 1) / 2);

        if (hm1 == null && hm2 == null)
        {
            return null;
        }

        List<T>[] hm;
        if (hm2 == null)
        {
            hm = hm1;
        }
        else if (hm1 == null)
        {
            hm = hm2;
        }
        else
        {
            // Both matched.  Select the longest.
            hm = hm1[4].Count > hm2[4].Count ? hm1 : hm2;
        }

        // A half-match was found, sort out the return data.
        if (text1.Length > text2.Length)
        {
            return hm;
            //return new string[]{hm[0], hm[1], hm[2], hm[3], hm[4]};
        }

        return [hm[2], hm[3], hm[0], hm[1], hm[4]];
    }

    /**
     * Does a Substring of shorttext exist within longtext such that the
     * Substring is at least half the length of longtext?
     * @param longtext Longer string.
     * @param shorttext Shorter string.
     * @param i Start index of quarter length Substring within longtext.
     * @return Five element string array, containing the prefix of longtext, the
     *     suffix of longtext, the prefix of shorttext, the suffix of shorttext
     *     and the common middle.  Or null if there was no match.
     */
    private List<T>[] diff_halfMatchI(ReadOnlySpan<T> longtext, ReadOnlySpan<T> shorttext, int i)
    {
        // Start with a 1/4 length Substring at position i as a seed.
        var seed = longtext.Slice(i, longtext.Length / 4);
        int j = -1;
        var best_common = new List<T>();
        var best_longtext_a = ReadOnlySpan<T>.Empty;
        var best_longtext_b = ReadOnlySpan<T>.Empty;
        var best_shorttext_a = ReadOnlySpan<T>.Empty;
        var best_shorttext_b = ReadOnlySpan<T>.Empty;
        while (j < shorttext.Length && (j = shorttext.IndexOf(seed, j + 1)) != -1)
        {
            int prefixLength = diff_commonPrefix(longtext.Slice(i), shorttext.Slice(j));
            int suffixLength = diff_commonSuffix(longtext.Slice(0, i), shorttext.Slice(0, j));
            if (best_common.Count < suffixLength + prefixLength)
            {
                best_common = shorttext.Slice(j - suffixLength, suffixLength).ToList();
                best_common.AddRange(shorttext.Slice(j, prefixLength));
                best_longtext_a = longtext.Slice(0, i - suffixLength);
                best_longtext_b = longtext.Slice(i + prefixLength);
                best_shorttext_a = shorttext.Slice(0, j - suffixLength);
                best_shorttext_b = shorttext.Slice(j + prefixLength);
            }
        }

        if (best_common.Count * 2 >= longtext.Length)
        {
            return
            [
                best_longtext_a.ToList(), best_longtext_b.ToList(), best_shorttext_a.ToList(),
                best_shorttext_b.ToList(), best_common
            ];
        }

        return null;
    }

    /**
     * Reduce the number of edits by eliminating semantically trivial
     * equalities.
     * @param diffs List of Diff objects.
     */
    public void diff_cleanupSemantic(List<Diff<T>> diffs)
    {
        bool changes = false;
        // Stack of indices where equalities are found.
        Stack<int> equalities = new Stack<int>();
        // Always equal to equalities[equalitiesLength-1][1]
        List<T> lastEquality = null;
        int pointer = 0; // Index of current position.
        // Number of characters that changed prior to the equality.
        int length_insertions1 = 0;
        int length_deletions1 = 0;
        // Number of characters that changed after the equality.
        int length_insertions2 = 0;
        int length_deletions2 = 0;
        while (pointer < diffs.Count)
        {
            if (diffs[pointer].operation == Operation.EQUAL)
            {
                // Equality found.
                equalities.Push(pointer);
                length_insertions1 = length_insertions2;
                length_deletions1 = length_deletions2;
                length_insertions2 = 0;
                length_deletions2 = 0;
                lastEquality = diffs[pointer].text;
            }
            else
            {
                // an insertion or deletion
                if (diffs[pointer].operation == Operation.INSERT)
                {
                    length_insertions2 += diffs[pointer].text.Count;
                }
                else
                {
                    length_deletions2 += diffs[pointer].text.Count;
                }

                // Eliminate an equality that is smaller or equal to the edits on both
                // sides of it.
                if (lastEquality != null && lastEquality.Count <= Math.Max(length_insertions1, length_deletions1)
                                         && lastEquality.Count <= Math.Max(length_insertions2, length_deletions2))
                {
                    // Duplicate record.
                    diffs.Insert(equalities.Peek(), new(Operation.DELETE, lastEquality));
                    // Change second copy to insert.
                    diffs[equalities.Peek() + 1].operation = Operation.INSERT;
                    // Throw away the equality we just deleted.
                    equalities.Pop();
                    if (equalities.Count > 0)
                    {
                        equalities.Pop();
                    }

                    pointer = equalities.Count > 0 ? equalities.Peek() : -1;
                    length_insertions1 = 0; // Reset the counters.
                    length_deletions1 = 0;
                    length_insertions2 = 0;
                    length_deletions2 = 0;
                    lastEquality = null;
                    changes = true;
                }
            }

            pointer++;
        }

        // Normalize the diff.
        if (changes)
        {
            diff_cleanupMerge(diffs);
        }

        diff_cleanupSemanticLossless(diffs);

        // Find any overlaps between deletions and insertions.
        // e.g: <del>abcxxx</del><ins>xxxdef</ins>
        //   -> <del>abc</del>xxx<ins>def</ins>
        // e.g: <del>xxxabc</del><ins>defxxx</ins>
        //   -> <ins>def</ins>xxx<del>abc</del>
        // Only extract an overlap if it is as big as the edit ahead or behind it.
        pointer = 1;
        while (pointer < diffs.Count)
        {
            if (diffs[pointer - 1].operation == Operation.DELETE &&
                diffs[pointer].operation == Operation.INSERT)
            {
                var deletion = diffs[pointer - 1].text;
                var insertion = diffs[pointer].text;
                int overlap_length1 = diff_commonOverlap(deletion, insertion);
                int overlap_length2 = diff_commonOverlap(insertion, deletion);
                if (overlap_length1 >= overlap_length2)
                {
                    if (overlap_length1 >= deletion.Count / 2.0 || overlap_length1 >= insertion.Count / 2.0)
                    {
                        // Overlap found.
                        // Insert an equality and trim the surrounding edits.
                        diffs.Insert(pointer, new(Operation.EQUAL, insertion.Slice(0, overlap_length1)));
                        diffs[pointer - 1].text = deletion.Slice(0, deletion.Count - overlap_length1);
                        diffs[pointer + 1].text = insertion.Slice(overlap_length1);
                        pointer++;
                    }
                }
                else
                {
                    if (overlap_length2 >= deletion.Count / 2.0 ||
                        overlap_length2 >= insertion.Count / 2.0)
                    {
                        // Reverse overlap found.
                        // Insert an equality and swap and trim the surrounding edits.
                        diffs.Insert(pointer, new(Operation.EQUAL, deletion.Slice(0, overlap_length2)));
                        diffs[pointer - 1].operation = Operation.INSERT;
                        diffs[pointer - 1].text = insertion.Slice(0, insertion.Count - overlap_length2);
                        diffs[pointer + 1].operation = Operation.DELETE;
                        diffs[pointer + 1].text = deletion.Slice(overlap_length2);
                        pointer++;
                    }
                }

                pointer++;
            }

            pointer++;
        }
    }

    /**
     * Look for single edits surrounded on both sides by equalities
     * which can be shifted sideways to align the edit to a word boundary.
     * e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.
     * @param diffs List of Diff objects.
     */
    public void diff_cleanupSemanticLossless(List<Diff<T>> diffs)
    {
        int pointer = 1;
        // Intentionally ignore the first and last element (don't need checking).
        while (pointer < diffs.Count - 1)
        {
            if (diffs[pointer - 1].operation == Operation.EQUAL &&
                diffs[pointer + 1].operation == Operation.EQUAL)
            {
                // This is a single edit surrounded by equalities.
                var equality1 = diffs[pointer - 1].text.Slice(0);
                var edit = diffs[pointer].text.Slice(0);
                var equality2 = diffs[pointer + 1].text.Slice(0);

                // First, shift the edit as far left as possible.
                int commonOffset = diff_commonSuffix(equality1.AsSpan(), edit.AsSpan());
                if (commonOffset > 0)
                {
                    var commonString = edit.Slice(edit.Count - commonOffset);
                    equality1 = equality1.Slice(0, equality1.Count - commonOffset);
                    var subEdit = edit.Slice(0, edit.Count - commonOffset);
                    edit = commonString.Slice(0);
                    edit.AddRange(subEdit);
                    equality2.InsertRange(0, commonString.Slice(0));
                }

                // Second, step character by character right,
                // looking for the best fit.
                var bestEquality1 = equality1.Slice(0);
                var bestEdit = edit.Slice(0);
                var bestEquality2 = equality2.Slice(0);
                int bestScore = diff_cleanupSemanticScore(equality1, edit) + diff_cleanupSemanticScore(edit, equality2);
                while (edit.Count != 0 && equality2.Count != 0 && edit[0].Equals(equality2[0]))
                {
                    equality1.Add(edit[0]);
                    edit = edit.Slice(1);
                    edit.Add(equality2[0]);
                    equality2 = equality2.Slice(1);
                    int score = diff_cleanupSemanticScore(equality1, edit) + diff_cleanupSemanticScore(edit, equality2);
                    // The >= encourages trailing rather than leading whitespace on
                    // edits.
                    if (score >= bestScore)
                    {
                        bestScore = score;
                        bestEquality1 = equality1.Slice(0);
                        bestEdit = edit;
                        bestEquality2 = equality2.Slice(0);
                    }
                }

                if (!diffs[pointer - 1].text.Equals(bestEquality1))
                {
                    // We have an improvement, save it back to the diff.
                    if (bestEquality1.Count != 0)
                    {
                        diffs[pointer - 1].text = bestEquality1.Slice(0);
                    }
                    else
                    {
                        diffs.RemoveAt(pointer - 1);
                        pointer--;
                    }

                    diffs[pointer].text = bestEdit.Slice(0);
                    if (bestEquality2.Count != 0)
                    {
                        diffs[pointer + 1].text = bestEquality2.Slice(0);
                    }
                    else
                    {
                        diffs.RemoveAt(pointer + 1);
                        pointer--;
                    }
                }
            }

            pointer++;
        }
    }

    /**
     * Given two strings, compute a score representing whether the internal
     * boundary falls on logical boundaries.
     * Scores range from 6 (best) to 0 (worst).
     * @param one First string.
     * @param two Second string.
     * @return The score.
     */
    private int diff_cleanupSemanticScore(List<T> one, List<T> two)
    {
        if (one.Count == 0 || two.Count == 0)
        {
            // Edges are the best.
            return 6;
        }

        // Each port of this function behaves slightly differently due to
        // subtle differences in each language's definition of things like
        // 'whitespace'.  Since this function's purpose is largely cosmetic,
        // the choice has been made to use each language's native features
        // rather than force total conformity.
        var char1 = one[one.Count - 1];
        var char2 = two[0];
        bool nonAlphaNumeric1 = !char1.IsLetterOrDigit();
        bool nonAlphaNumeric2 = !char2.IsLetterOrDigit();
        bool whitespace1 = nonAlphaNumeric1 && char1.IsWhiteSpace();
        bool whitespace2 = nonAlphaNumeric2 && char2.IsWhiteSpace();
        bool lineBreak1 = whitespace1 && char1.IsControl();
        bool lineBreak2 = whitespace2 && char2.IsControl();
        bool blankLine1 = lineBreak1 && char1.IsBlankLineEnd(one);
        bool blankLine2 = lineBreak2 && char2.IsBlankLineStart(two);

        if (blankLine1 || blankLine2)
        {
            // Five points for blank lines.
            return 5;
        }
        
        if (lineBreak1 || lineBreak2)
        {
            // Four points for line breaks.
            return 4;
        }
        
        if (nonAlphaNumeric1 && !whitespace1 && whitespace2)
        {
            // Three points for end of sentences.
            return 3;
        }
        
        if (whitespace1 || whitespace2)
        {
            // Two points for whitespace.
            return 2;
        }
        
        if (nonAlphaNumeric1 || nonAlphaNumeric2)
        {
            // One point for non-alphanumeric.
            return 1;
        }

        return 0;
    }

    /**
     * Reduce the number of edits by eliminating operationally trivial
     * equalities.
     * @param diffs List of Diff objects.
     */
    public void diff_cleanupEfficiency(List<Diff<T>> diffs)
    {
        bool changes = false;
        // Stack of indices where equalities are found.
        Stack<int> equalities = new Stack<int>();
        // Always equal to equalities[equalitiesLength-1][1]
        var lastEquality = new List<T>();
        int pointer = 0; // Index of current position.
        // Is there an insertion operation before the last equality.
        bool pre_ins = false;
        // Is there a deletion operation before the last equality.
        bool pre_del = false;
        // Is there an insertion operation after the last equality.
        bool post_ins = false;
        // Is there a deletion operation after the last equality.
        bool post_del = false;
        while (pointer < diffs.Count)
        {
            if (diffs[pointer].operation == Operation.EQUAL)
            {
                // Equality found.
                if (diffs[pointer].text.Count < Diff_EditCost && (post_ins || post_del))
                {
                    // Candidate found.
                    equalities.Push(pointer);
                    pre_ins = post_ins;
                    pre_del = post_del;
                    lastEquality = diffs[pointer].text;
                }
                else
                {
                    // Not a candidate, and can never become one.
                    equalities.Clear();
                    lastEquality = new();
                }

                post_ins = post_del = false;
            }
            else
            {
                // An insertion or deletion.
                if (diffs[pointer].operation == Operation.DELETE)
                {
                    post_del = true;
                }
                else
                {
                    post_ins = true;
                }

                /*
                 * Five types to be split:
                 * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
                 * <ins>A</ins>X<ins>C</ins><del>D</del>
                 * <ins>A</ins><del>B</del>X<ins>C</ins>
                 * <ins>A</del>X<ins>C</ins><del>D</del>
                 * <ins>A</ins><del>B</del>X<del>C</del>
                 */
                if (lastEquality.Count != 0 &&
                    ((pre_ins && pre_del && post_ins && post_del) ||
                     (lastEquality.Count < Diff_EditCost / 2 &&
                      (pre_ins ? 1 : 0) + (pre_del ? 1 : 0) + (post_ins ? 1 : 0) + (post_del ? 1 : 0) == 3)))
                {
                    // Duplicate record.
                    diffs.Insert(equalities.Peek(), new(Operation.DELETE, lastEquality));
                    // Change second copy to insert.
                    diffs[equalities.Peek() + 1].operation = Operation.INSERT;
                    equalities.Pop(); // Throw away the equality we just deleted.
                    lastEquality = new();
                    if (pre_ins && pre_del)
                    {
                        // No changes made which could affect previous entry, keep going.
                        post_ins = post_del = true;
                        equalities.Clear();
                    }
                    else
                    {
                        if (equalities.Count > 0)
                        {
                            equalities.Pop();
                        }

                        pointer = equalities.Count > 0 ? equalities.Peek() : -1;
                        post_ins = post_del = false;
                    }

                    changes = true;
                }
            }

            pointer++;
        }

        if (changes)
        {
            diff_cleanupMerge(diffs);
        }
    }

    /**
     * Reorder and merge like edit sections.  Merge equalities.
     * Any edit section can move as long as it doesn't cross an equality.
     * @param diffs List of Diff objects.
     */
    public void diff_cleanupMerge(List<Diff<T>> diffs)
    {
        // Add a dummy entry at the end.
        diffs.Add(new(Operation.EQUAL, new()));
        int pointer = 0;
        int count_delete = 0;
        int count_insert = 0;
        var text_delete = new List<T>();
        var text_insert = new List<T>();
        int commonlength;
        while (pointer < diffs.Count)
        {
            switch (diffs[pointer].operation)
            {
                case Operation.INSERT:
                    count_insert++;
                    text_insert.AddRange(diffs[pointer].text);
                    pointer++;
                    break;
                case Operation.DELETE:
                    count_delete++;
                    text_delete.AddRange(diffs[pointer].text);
                    pointer++;
                    break;
                case Operation.EQUAL:
                    // Upon reaching an equality, check for prior redundancies.
                    if (count_delete + count_insert > 1)
                    {
                        if (count_delete != 0 && count_insert != 0)
                        {
                            // Factor out any common prefixies.
                            commonlength = diff_commonPrefix(text_insert.AsSpan(), text_delete.AsSpan());
                            if (commonlength != 0)
                            {
                                if (pointer - count_delete - count_insert > 0 && diffs[pointer - count_delete - count_insert - 1].operation == Operation.EQUAL)
                                {
                                    diffs[pointer - count_delete - count_insert - 1].text.AddRange(text_insert.Slice(0, commonlength));
                                }
                                else
                                {
                                    diffs.Insert(0, new(Operation.EQUAL, text_insert.Slice(0, commonlength)));
                                    pointer++;
                                }

                                text_insert = text_insert.Slice(commonlength);
                                text_delete = text_delete.Slice(commonlength);
                            }

                            // Factor out any common suffixies.
                            commonlength = diff_commonSuffix(text_insert.AsSpan(), text_delete.AsSpan());
                            if (commonlength != 0)
                            {
                                var oldValue = diffs[pointer].text.Slice(0);
                                diffs[pointer].text = text_insert.Slice(text_insert.Count - commonlength);
                                diffs[pointer].text.AddRange(oldValue);
                                text_insert = text_insert.Slice(0, text_insert.Count - commonlength);
                                text_delete = text_delete.Slice(0, text_delete.Count - commonlength);
                            }
                        }

                        // Delete the offending records and add the merged ones.
                        pointer -= count_delete + count_insert;
                        diffs.Splice(pointer, count_delete + count_insert);
                        if (text_delete.Count != 0)
                        {
                            diffs.Splice(pointer, 0, new Diff<T>(Operation.DELETE, text_delete));
                            pointer++;
                        }

                        if (text_insert.Count != 0)
                        {
                            diffs.Splice(pointer, 0, new Diff<T>(Operation.INSERT, text_insert));
                            pointer++;
                        }

                        pointer++;
                    }
                    else if (pointer != 0 && diffs[pointer - 1].operation == Operation.EQUAL)
                    {
                        // Merge this equality with the previous one.
                        diffs[pointer - 1].text.AddRange(diffs[pointer].text);
                        diffs.RemoveAt(pointer);
                    }
                    else
                    {
                        pointer++;
                    }

                    count_insert = 0;
                    count_delete = 0;
                    text_delete.Clear();
                    text_insert.Clear();
                    break;
            }
        }

        if (diffs[diffs.Count - 1].text.Count == 0)
        {
            diffs.RemoveAt(diffs.Count - 1); // Remove the dummy entry at the end.
        }

        // Second pass: look for single edits surrounded on both sides by
        // equalities which can be shifted sideways to eliminate an equality.
        // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
        bool changes = false;
        pointer = 1;
        // Intentionally ignore the first and last element (don't need checking).
        while (pointer < (diffs.Count - 1))
        {
            if (diffs[pointer - 1].operation == Operation.EQUAL &&
                diffs[pointer + 1].operation == Operation.EQUAL)
            {
                // This is a single edit surrounded by equalities.
                if (diffs[pointer].text.EndsWith(diffs[pointer - 1].text))
                {
                    var addValue = diffs[pointer].text.Slice(0, diffs[pointer].text.Count - diffs[pointer - 1].text.Count);
                    // Shift the edit over the previous equality. todo bug
                    diffs[pointer].text = diffs[pointer - 1].text.Slice(0);
                    diffs[pointer].text.AddRange(addValue);

                    addValue = diffs[pointer + 1].text.Slice(0);
                    diffs[pointer + 1].text = diffs[pointer - 1].text.Slice(0);
                    diffs[pointer + 1].text.AddRange(addValue);
                    diffs.Splice(pointer - 1, 1);
                    changes = true;
                }
                else if (diffs[pointer].text.StartsWith(diffs[pointer + 1].text))
                {
                    // Shift the edit over the next equality.
                    diffs[pointer - 1].text.AddRange(diffs[pointer + 1].text);
                    diffs[pointer].text = diffs[pointer].text.Slice(diffs[pointer + 1].text.Count);
                    diffs[pointer].text.AddRange(diffs[pointer + 1].text);
                    diffs.Splice(pointer + 1, 1);
                    changes = true;
                }
            }

            pointer++;
        }

        // If shifts were made, the diff needs reordering and another shift sweep.
        if (changes)
        {
            diff_cleanupMerge(diffs);
        }
    }

    /**
     * loc is a location in text1, compute and return the equivalent location in
     * text2.
     * e.g. "The cat" vs "The big cat", 1->1, 5->8
     * @param diffs List of Diff objects.
     * @param loc Location within text1.
     * @return Location within text2.
     */
    public int diff_xIndex(List<Diff<T>> diffs, int loc)
    {
        int chars1 = 0;
        int chars2 = 0;
        int last_chars1 = 0;
        int last_chars2 = 0;
        Diff<T> lastDiff = null;
        foreach (var aDiff in diffs)
        {
            if (aDiff.operation != Operation.INSERT)
            {
                // Equality or deletion.
                chars1 += aDiff.text.Count;
            }

            if (aDiff.operation != Operation.DELETE)
            {
                // Equality or insertion.
                chars2 += aDiff.text.Count;
            }

            if (chars1 > loc)
            {
                // Overshot the location.
                lastDiff = aDiff;
                break;
            }

            last_chars1 = chars1;
            last_chars2 = chars2;
        }

        if (lastDiff != null && lastDiff.operation == Operation.DELETE)
        {
            // The location was deleted.
            return last_chars2;
        }

        // Add the remaining character length.
        return last_chars2 + (loc - last_chars1);
    }

    /**
     * Convert a Diff list into a pretty HTML report.
     * @param diffs List of Diff objects.
     * @return HTML representation.
     */
    public string diff_prettyHtml(List<Diff<T>> diffs)
    {
        StringBuilder html = new StringBuilder();
        foreach (var aDiff in diffs)
        {
            var text = aDiff.ToElementString().Replace("&", "&amp;").Replace("<", "&lt;")
                .Replace(">", "&gt;").Replace("\n", "&para;<br>");
            switch (aDiff.operation)
            {
                case Operation.INSERT:
                    html.Append("<ins style=\"background:#e6ffe6;\">").Append(text)
                        .Append("</ins>");
                    break;
                case Operation.DELETE:
                    html.Append("<del style=\"background:#ffe6e6;\">").Append(text)
                        .Append("</del>");
                    break;
                case Operation.EQUAL:
                    html.Append("<span>").Append(text).Append("</span>");
                    break;
            }
        }

        return html.ToString();
    }

    /**
     * Compute and return the source text (all equalities and deletions).
     * @param diffs List of Diff objects.
     * @return Source text.
     */
    public List<T> diff_text1(List<Diff<T>> diffs)
    {
        var result = new List<T>();
        foreach (var aDiff in diffs)
        {
            if (aDiff.operation != Operation.INSERT)
            {
                result.AddRange(aDiff.text);
            }
        }

        return result;
    }

    /**
     * Compute and return the destination text (all equalities and insertions).
     * @param diffs List of Diff objects.
     * @return Destination text.
     */
    public List<T> diff_text2(List<Diff<T>> diffs)
    {
        var result = new List<T>();
        foreach (var aDiff in diffs)
        {
            if (aDiff.operation != Operation.DELETE)
            {
                result.AddRange(aDiff.text);
            }
        }

        return result;
    }

    /**
     * Compute the Levenshtein distance; the number of inserted, deleted or
     * substituted characters.
     * @param diffs List of Diff objects.
     * @return Number of changes.
     */
    public int diff_levenshtein(List<Diff<T>> diffs)
    {
        int levenshtein = 0;
        int insertions = 0;
        int deletions = 0;
        foreach (var aDiff in diffs)
        {
            switch (aDiff.operation)
            {
                case Operation.INSERT:
                    insertions += aDiff.text.Count;
                    break;
                case Operation.DELETE:
                    deletions += aDiff.text.Count;
                    break;
                case Operation.EQUAL:
                    // A deletion and an insertion is one substitution.
                    levenshtein += Math.Max(insertions, deletions);
                    insertions = 0;
                    deletions = 0;
                    break;
            }
        }

        levenshtein += Math.Max(insertions, deletions);
        return levenshtein;
    }

    /**
     * Crush the diff into an encoded string which describes the operations
     * required to transform text1 into text2.
     * E.g. =3\t-2\t+ing  -> Keep 3 chars, delete 2 chars, insert 'ing'.
     * Operations are tab-separated.  Inserted text is escaped using %xx
     * notation.
     * @param diffs Array of Diff objects.
     * @return Delta text.
     */
    public string diff_toDelta(List<Diff<T>> diffs)
    {
        StringBuilder text = new StringBuilder();
        foreach (var aDiff in diffs)
        {
            switch (aDiff.operation)
            {
                case Operation.INSERT:
                    text.Append("+").Append(encodeURI(aDiff.ToElementString())).Append("\t");
                    break;
                case Operation.DELETE:
                    text.Append("-").Append(aDiff.text.Count).Append("\t");
                    break;
                case Operation.EQUAL:
                    text.Append("=").Append(aDiff.text.Count).Append("\t");
                    break;
            }
        }

        string delta = text.ToString();
        if (delta.Length != 0)
        {
            // Strip off trailing tab character.
            delta = delta.Substring(0, delta.Length - 1);
        }

        return delta;
    }

    //  PATCH FUNCTIONS

    /**
     * Compute a list of patches to turn text1 into text2.
     * A set of diffs will be computed.
     * @param text1 Old text.
     * @param text2 New text.
     * @return List of Patch objects.
     */
    public List<Patch<T>> patch_make(List<T> text1, List<T> text2)
    {
        // Check for null inputs not needed since null can't be passed in C#.
        // No diffs provided, compute our own.
        var diffs = diff_main(text1, text2);
        if (diffs.Count > 2)
        {
            diff_cleanupSemantic(diffs);
            diff_cleanupEfficiency(diffs);
        }

        return patch_make(text1, diffs);
    }

    /**
     * Compute a list of patches to turn text1 into text2.
     * text1 will be derived from the provided diffs.
     * @param diffs Array of Diff objects for text1 to text2.
     * @return List of Patch objects.
     */
    public List<Patch<T>> patch_make(List<Diff<T>> diffs)
    {
        // Check for null inputs not needed since null can't be passed in C#.
        // No origin string provided, compute our own.
        var text1 = diff_text1(diffs);
        return patch_make(text1, diffs);
    }

    /**
     * Compute a list of patches to turn text1 into text2.
     * text2 is not provided, diffs are the delta between text1 and text2.
     * @param text1 Old text.
     * @param diffs Array of Diff objects for text1 to text2.
     * @return List of Patch objects.
     */
    public List<Patch<T>> patch_make(List<T> text1, List<Diff<T>> diffs)
    {
        int diffLength = 0;
        foreach (var diff in diffs)
        {
            if (diff.operation != Operation.INSERT)
            {
                diffLength += diff.text.Count;
            }
        }

        if (diffLength > text1.Count)
        {
            throw new Exception("diff 修改和等于原文本的长度大于原文本总长度");
        }

        // Check for null inputs not needed since null can't be passed in C#.
        var patches = new List<Patch<T>>();
        if (diffs.Count == 0)
        {
            return patches; // Get rid of the null case.
        }

        var patch = new Patch<T>();
        int count = 0; // Number of characters into the text1 string.
        int index = 0;
        foreach (var aDiff in diffs)
        {
            index++;
            // Update the current character count.
            if (aDiff.operation != Operation.INSERT)
            {
                count += aDiff.text.Count;
            }

            switch (aDiff.operation)
            {
                case Operation.INSERT:
                    patch.diffs.Add(aDiff);
                    patch.insertLength += aDiff.text.Count;
                    break;
                case Operation.DELETE:
                    patch.deleteLength += aDiff.text.Count;
                    patch.diffs.Add(aDiff);
                    break;
                case Operation.EQUAL:
                    if (patch.diffs.Count != 0)
                    {
                        patches.Add(patch);
                        patch = new Patch<T>
                        {
                            start = count
                        };
                    }
                    else
                    {
                        patch.start = count;
                    }

                    break;
            }
        }

        // Pick up the leftover patch if not empty.
        if (patch.diffs.Count != 0)
        {
            patches.Add(patch);
        }

        return patches;
    }

    /**
     * Given an array of patches, return another array that is identical.
     * @param patches Array of Patch objects.
     * @return Array of Patch objects.
     */
    public List<Patch<T>> patch_deepCopy(List<Patch<T>> patches)
    {
        var patchesCopy = new List<Patch<T>>();
        foreach (var aPatch in patches)
        {
            var patchCopy = new Patch<T>();
            foreach (var aDiff in aPatch.diffs)
            {
                var diffCopy = new Diff<T>(aDiff.operation, aDiff.text);
                patchCopy.diffs.Add(diffCopy);
            }

            patchCopy.start = aPatch.start;
            patchCopy.insertLength = aPatch.insertLength;
            patchCopy.deleteLength = aPatch.deleteLength;
            patchesCopy.Add(patchCopy);
        }

        return patchesCopy;
    }
    
    public static (List<Patch<T>> selfRemainPatches,List<Patch<T>> otherRemainPatches, List<Patch<T>> mergedPatches) 
        patch_try_merge(List<Patch<T>> patches1, List<Patch<T>> patches2)
    {
        if (patches1.Count == 0)
        {
            return (new(),new(), patches2.Slice(0));
        }

        if (patches2.Count == 0)
        {
            return (new(),new(), patches1.Slice(0));
        }

        var patches = new List<Patch<T>>();
        int index1 = 0;
        int index2 = 0;
        while (index1 < patches1.Count && index2 < patches2.Count)
        {
            (int left, int right) range1 = (patches1[index1].start, patches1[index1].start + patches1[index1].deleteLength - 1);
            (int left, int right) range2 = (patches2[index2].start, patches2[index2].start + patches2[index2].deleteLength - 1);

            if (patches1[index1].Equals(patches2[index2]))
            {
                patches.Add(patches1[index1]);
                index1++;
                index2++;
                continue;
            }
            
            if (range1.left == range2.left ||
                range1.left < range2.left && range1.right >= range2.left ||
                range2.left < range1.left && range2.right >= range1.left)
            {
                return (patches1.Slice(index1),patches2.Slice(index2), patches);
            }

            if (range1.left > range2.left)
            {
                patches.Add(patches2[index2]);
                index2++;
            }
            else
            {
                patches.Add(patches1[index1]);
                index1++;
            }
        }

        if (index1 < patches1.Count)
        {
            patches.AddRange(patches1.GetRange(index1, patches1.Count - index1));
        }

        if (index2 < patches2.Count)
        {
            patches.AddRange(patches2.GetRange(index2, patches2.Count - index2));
        }

        return (new(),new(), patches);
    }
    
    /**
     * Merge a set of patches onto the text.  Return a patched text, as well
     * as an array of true/false values indicating which patches were applied.
     * @param patches Array of Patch objects
     * @param text Old text.
     * @return Two element Object array, containing the new text and an array of
     *      bool values.
     */
    public static List<T> patch_apply(List<Patch<T>> patches, List<T> patchText,out int originIndex,bool returnAll = true)
    {
        if (patches.Count == 0)
        {
            if (returnAll)
            {
                originIndex = patchText.Count;
                return patchText.Slice(0);
            }

            originIndex = 0;
            return new();
        }

        var text = new List<T>();
        var index = 0;
        foreach (var patch in patches)
        {
            if (patch.start > index)
            {
                for (int i = index; i < patch.start; i++)
                {
                    text.Add(patchText[i].DeepCopy());
                }
                index = patch.start;
            }

            foreach (var diff in patch.diffs)
            {
                switch (diff.operation)
                {
                    case Operation.INSERT:
                        for (int i = 0; i < diff.text.Count; i++)
                        {
                            var item = diff.text[i].DeepCopy();
                            item.PatchedState = i < patch.deleteLength ? PatchState.Change : PatchState.Insert;
                            text.Add(item);
                        }
                        break;
                    case Operation.DELETE:
                        index += diff.text.Count;
                        break;
                }
            }
        }

        originIndex = index;
        if (index < patchText.Count && returnAll)
        {
            text.AddRange(patchText.Slice(index));
            originIndex = patchText.Count;
        }

        return text;
    }

    /**
     * Take a list of patches and return a textual representation.
     * @param patches List of Patch objects.
     * @return Text representation of patches.
     */
    public string patch_toText(List<Patch<T>> patches)
    {
        StringBuilder text = new StringBuilder();
        foreach (var aPatch in patches)
        {
            text.Append(aPatch);
        }

        return text.ToString();
    }

    /**
     * Encodes a string with URI-style % escaping.
     * Compatible with JavaScript's encodeURI function.
     *
     * @param str The string to encode.
     * @return The encoded string.
     */
    public static string encodeURI(string str)
    {
        // C# is overzealous in the replacements.  Walk back on a few.
        return new StringBuilder(HttpUtility.UrlEncode(str))
            .Replace('+', ' ').Replace("%20", " ").Replace("%21", "!")
            .Replace("%2a", "*").Replace("%27", "'").Replace("%28", "(")
            .Replace("%29", ")").Replace("%3b", ";").Replace("%2f", "/")
            .Replace("%3f", "?").Replace("%3a", ":").Replace("%40", "@")
            .Replace("%26", "&").Replace("%3d", "=").Replace("%2b", "+")
            .Replace("%24", "$").Replace("%2c", ",").Replace("%23", "#")
            .Replace("%7e", "~")
            .ToString();
    }
}